package leetcode.sword;

public class Solution11 {
    public int minArray(int[] numbers) {
        //旋转的地方就是数组最小值，旋转后呈山谷形，谷底即是旋转位置，也是最小值
        //最简单的方法是遍历找第一个递减的数字，复杂度O(n)
        //二分法或许更好，目的是找到右支第一个数字，设下标x
        int l = 0, r = numbers.length-1, mid = 0;
        while (l<r){
            mid = (l+r)>>1;
            if(numbers[mid]>numbers[r]){ //mid在左支，旋转点在[mid+1,r]
                l = mid + 1;
            }else if(numbers[mid]<numbers[r]){ //mid在右支，旋转点在[mid,r]
                r = mid;
            }else { //mid可能在左支或者右支，收缩左支边界
                //如果x<r,r收缩后x还在[l,r]搜索区间
                //如果x=r,而且此时l<=m<r=x,这说明m在左支，那么nums[x]<=nums[l]<=...<=nums[m]=nums[r]=nums[x]，所以nums[l]=...=nums[m]=nums[r]
                //r收缩后，搜索范围变成[l,...,m,...,r-1],这是个单增的区间，经过二分查找最终停在l上，而nums[l]=nums[r]，所以最终结果是对的
                r = r - 1;
            }
        }
        return numbers[mid];
    }
}
